#include <iostream>
#include <vector>

using namespace std;

void merge_sort(vector<int> &vec, vector<int> &vecTemp, int left, int right)
{
    //1.划分
    if(left >= right) //递归终止的条件
        return;
    int mid = left + (right-left)/2;
    int start1 = left;
    int end1 = mid;
    int start2 = mid + 1;
    int end2 = right;
    
    merge_sort(vec,vecTemp,start1,end1); //递归划分左半区
    merge_sort(vec,vecTemp,start2,end2); //递归划分右半区

    //2.合并
    int index = left; //创建临时数组vecTemp的下标
    while(start1 <= end1 && start2 <= end2)
    {
        if(vec[start1] < vec[start2])         //左半区的第一个元素小于右半区的第一个元素
        {
            vecTemp[index++] = vec[start1++]; //将小的数放到临时数组里面，并将左半区和临时数组的指针右移
        }
        else                                  //左半区的第一个元素小于右半区的第一个元素
        {
            vecTemp[index++] = vec[start2++]; //将小的数放到临时数组里面，并将右半区和临时数组的指针右移
        }
    }

    while(start1 <= end1)
    {
        vecTemp[index++] = vec[start1++];    //合并左半区剩余的元素
    }
    while(start2 <= end2)
    {
        vecTemp[index++] = vec[start2++];    //合并右半区剩余的元素
    }
    while(left <= right)
    {
       vec[left] = vecTemp[left];   //将临时数组中的元素复制回原来的数组
       left++;
    }
    //for(index = left; index <= right; ++index)
    //{
    //    vec[index] = vecTemp[index];
    //}
}

int main()
{
    int num;
    cin >> num;

    vector<int> vec;
    int temp;
    for(int i = 0; i < num; ++i)
    {
        cin >> temp;
        vec.push_back(temp);
    }
    
    vector<int> vecTemp(num); //vector<int> vecTemp; 不能这样写，需要确定数组的个数，否则出现错误：Segmentation fault，内存非法访问

    merge_sort(vec,vecTemp,0,num-1);

    for(vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}
